{
  "cells": [
    {
      "cell_type": "markdown",
      "metadata": {},
      "source": [
        "# SymbolicEliminationTree"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {},
      "source": [
        "A `SymbolicEliminationTree` represents the computational structure used in variable elimination, particularly in sparse Cholesky or QR factorization. Each node in the tree corresponds to the elimination of a single variable.\n",
        "\n",
        "The tree structure reveals dependencies: the elimination of a variable (node) depends on the results from its children in the tree. The root of the tree corresponds to the last variable eliminated. This structure is closely related to the resulting Bayes net or Bayes tree."
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {},
      "source": [
        "<a href=\"https://colab.research.google.com/github/borglab/gtsam/blob/develop/gtsam/symbolic/doc/SymbolicEliminationTree.ipynb\" target=\"_parent\"><img src=\"https://colab.research.google.com/assets/colab-badge.svg\" alt=\"Open In Colab\"/></a>"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "tags": [
          "remove-cell"
        ]
      },
      "outputs": [],
      "source": [
        "%pip install --quiet gtsam-develop"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {},
      "outputs": [],
      "source": [
        "from gtsam import SymbolicEliminationTree, SymbolicFactorGraph, Ordering\n",
        "from gtsam.symbol_shorthand import X, L"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {},
      "source": [
        "## Creating a SymbolicEliminationTree\n",
        "\n",
        "An elimination tree is constructed from a `SymbolicFactorGraph` and an `Ordering`."
      ]
    },
    {
      "cell_type": "code",
      "execution_count": 4,
      "metadata": {},
      "outputs": [
        {
          "name": "stdout",
          "output_type": "stream",
          "text": [
            "Symbolic Elimination Tree:\n",
            "-(x2)\n",
            "Symbolic Elimination Tree:\n",
            "| -(x1)\n",
            "Symbolic Elimination Tree:\n",
            "| -  x1 x2\n",
            "Symbolic Elimination Tree:\n",
            "| | -(x0)\n",
            "Symbolic Elimination Tree:\n",
            "| | -  x0\n",
            "Symbolic Elimination Tree:\n",
            "| | -  x0 x1\n",
            "Symbolic Elimination Tree:\n",
            "| | | -(l1)\n",
            "Symbolic Elimination Tree:\n",
            "| | | -  x0 l1\n",
            "Symbolic Elimination Tree:\n",
            "| | -(l2)\n",
            "Symbolic Elimination Tree:\n",
            "| | -  x1 l2\n"
          ]
        }
      ],
      "source": [
        "# Create a factor graph\n",
        "graph = SymbolicFactorGraph()\n",
        "graph.push_factor(X(0))\n",
        "graph.push_factor(X(0), X(1))\n",
        "graph.push_factor(X(1), X(2))\n",
        "graph.push_factor(X(0), L(1))\n",
        "graph.push_factor(X(1), L(2))\n",
        "\n",
        "# Define an elimination ordering\n",
        "ordering = Ordering([L(1), L(2), X(0), X(1), X(2)])  # Eliminate L(1) first, then X(0), X(1), X(2) last\n",
        "\n",
        "# Construct the elimination tree\n",
        "elimination_tree = SymbolicEliminationTree(graph, ordering)\n",
        "\n",
        "# Print the tree structure (text representation)\n",
        "elimination_tree.print(\"Symbolic Elimination Tree:\\n\")"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {},
      "source": [
        "*(Note: Direct visualization of the elimination tree structure isn't available via a simple `.dot()` method like factor graphs or Bayes nets/trees in the Python wrapper, but the print output shows the parent-child relationships.)*"
      ]
    }
  ],
  "metadata": {
    "kernelspec": {
      "display_name": "py312",
      "language": "python",
      "name": "python3"
    },
    "language_info": {
      "codemirror_mode": {
        "name": "ipython",
        "version": 3
      },
      "file_extension": ".py",
      "mimetype": "text/x-python",
      "name": "python",
      "nbconvert_exporter": "python",
      "pygments_lexer": "ipython3",
      "version": "3.12.6"
    }
  },
  "nbformat": 4,
  "nbformat_minor": 4
}
